# -*- coding:utf-8
'''
作者: Jia
日期: 2022年04月22日
描述: https://leetcode-cn.com/problems/move-zeroes/
'''

from typing import List


class Solution:
    def moveZeroesI(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        创建新数组
        """
        cp_arr = []
        for num in nums:
            if num != 0:
                cp_arr.append(num)
        nums[:len(cp_arr)] = cp_arr[:]
        nums[len(cp_arr):] = [0] * (len(nums) - len(cp_arr))
    
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        记录每位向前移动的距离
        """
        n = len(nums)
        move_arr = [0] * n
        zero_num = 0
        for i, num in enumerate(nums):
            if num == 0:
                zero_num += 1
            else:
                move_arr[i] = zero_num
        
        for i, num in enumerate(nums):
            nums[i-move_arr[i]] = nums[i]
            if move_arr[i] != 0:
                nums[i] = 0
